A media recommendation service selects a user-specific subset of media items from the universe of available media items that the service determines may be enjoyed by the user. The selected media item can be provided to the user through a network to be rendered on a device of the user, such as a mobile device. A media item can be a song, video, animation, document or other media entity. When a user of the system begins a new session, the user can be associated with the subset of the recommended media items corresponding to the user.